package twobranchTree.preorderTraversal;

import java.util.ArrayList;
import java.util.List;

/**
 * @Date 2020/2/9
 * @author 王光浩
 * @Description 给出一个二叉树，使用前序遍历这个二叉树。
 * @Thinking 使用迭代方法——使用Morris二叉树遍历法。
 *           复杂度分析：时间复杂度O（n），空间复杂度O（n）——n为节点数
 */
public class MorrisMethod {
	public List<Integer> preorderTraversal(TreeNode root) {
		List<Integer> result=new ArrayList<Integer>();
		TreeNode node=root;
		TreeNode pointRoot=null;
		while(node!=null) {
			//当左节点为null，代表没有左子树，因此也就没有构成环的需要
			if(node.left==null) {  
				result.add(node.val);
				node=node.right;
			}
			//需要将左子树最后遍历到的节点与该子树的根节点相连接，这样当左子树遍历完成后可以顺利的进入右子树
			//所以该分支的目的就是将左子树的最后一个节点与根节点相连接
			else {  
				pointRoot=node.left;
				//找寻最后一个节点（去重）
				while(pointRoot.right!=null && pointRoot.right!=node){
					pointRoot=pointRoot.right;
				}
				//该左子树没有遍历过
				if(pointRoot.right==null) {
					result.add(node.val);
					pointRoot.right=node; //形成环
					node=node.left;       //继续遍历
				}
				else {
					pointRoot.right=null; //还原（不能更改数据的状态）
					node=node.right;
				}
			}
		}
		return result;
	}

	/**
	 * 采用 Morris遍历法 对二叉树进行遍历，时间复杂度为O（n），空间复杂度O（1）——（不包括保存结果的集合）
	 * @param root
	 * @return
	 */
	public List<Integer> preorderTraversal2(TreeNode root) {
		List<Integer> ret = new ArrayList<Integer>();
		if (root == null)
			return ret;
		TreeNode node = root;
		while (node != null) {
			if (node.left == null) {
				ret.add(node.val);
				node = node.right;
			}
			else {
				TreeNode next = node.left;
				while (next.right !=null && next.right != node)
					next = next.right;
				if (next.right == null) {
					ret.add(node.val);
					next.right = node;
					node = node.left;
				} else {
					node = node.right;
					next.right = null;
				}
			}
		}
		return ret;
	}
}
